cs / machine-learning

1. QR 分解

Eigenvalues of AATAA^T 以及 ATAA^TA 是 AA 的 squared singular values

QR 分解和 SVD(奇异值分解,Singular Value Decomposition)是线性代数中两种重要的矩阵分解方法,常用于数据分析、数值计算、信号处理等领域。


1. QR 分解

QR 分解是将一个矩阵分解为一个正交矩阵(Q)和一个上三角矩阵(R)的过程。

定义

如果 AA 是一个 m×nm \times n 的矩阵,且 m≥nm \geq n,那么 QR 分解可以表示为:

A=QR

其中:

  • QQ 是一个 m×mm \times m 的正交矩阵,满足 Q⊤Q=IQ^\top Q = I(正交矩阵的列是标准正交基向量)。
  • RR 是一个 m×nm \times n 的上三角矩阵。

用途

  • 求解线性方程组(如最小二乘问题)。
  • 数值算法(如 QR 算法,用于计算特征值)。
  • 信号处理和数据降维。

计算方法

  • Gram-Schmidt 正交化:对矩阵的列向量进行正交化。
  • Householder 反射:构造反射矩阵以逐步将矩阵转换为上三角形式。
  • Givens 旋转:使用旋转矩阵消除非对角线元素。

2. SVD 分解

SVD 分解是将一个矩阵分解为三个特殊矩阵的乘积。

定义

如果 AA 是一个 m×nm \times n 的矩阵,那么 SVD 可以表示为:

A=UΣV⊤A = U \Sigma V^\top

其中:

  • UU 是一个 m×mm \times m 的正交矩阵,其列是 AA⊤A A^\top 的特征向量。
  • Σ\Sigma 是一个 m×nm \times n 的对角矩阵,其对角线上的元素是 AA 的奇异值,按从大到小排序,其余元素为 0。
  • VV 是一个 n×nn \times n 的正交矩阵,其列是 A⊤AA^\top A 的特征向量。

用途

  • 数据降维(如主成分分析,PCA)。
  • 低秩近似(用于图像压缩或推荐系统)。
  • 求解病态线性系统。
  • 信号处理和特征提取。

计算方法

  • 奇异值通过计算 A⊤AA^\top A 和 AA⊤A A^\top 的特征值和特征向量获得。
  • 使用数值算法(如 Jacobi 方法或基于 QR 分解的算法)。

比较 QR 和 SVD

特性 QR 分解 SVD 分解
适用矩阵 方阵或任意矩阵 任意矩阵
分解形式 A=QRA = QR A=UΣV⊤A = U \Sigma V^\top
矩阵性质 正交矩阵和上三角矩阵 正交矩阵和对角矩阵
用途 数值计算、求解方程 数据降维、特征提取、矩阵近似
计算复杂度 较低(特别是方阵) 较高(但结果更强大)

总之,QR 分解偏向于数值线性代数的基本操作,而 SVD 分解具有更广泛的应用,在机器学习、数据处理等领域尤为重要。